#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 2000
#define M 200000
#define mod 998244353
using namespace std;
const int inv2=(mod+1)>>1;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
const int inf=(int)(1e9);
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
struct reads
{
	int num,data;
};
int c,T,n,m,t,ans,ans2,ans3,dp[N+1][2],F[N+1],DP[N+1],DPS[M+1],p[M+1],delta[N+1][N+1],dis[N+1][N+1],ds[N+1],pv[N+1][N+1],res[N+1];
vector<reads>E[N+1];
void add(int x,int y,int z)
{
	E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
	return;
}
bool cmp(int x,int y)
{
	return ds[x]>ds[y];
}
void bfs(int x)
{
	int top;
	queue<int>q;
	for (int i=1;i<=n;++i) dis[x][i]=inf;
	q.push(x),dis[x][x]=0,delta[x][x]=1;
	while (!q.empty())
	{
		top=q.front(),q.pop();
		for (int i=0;i<E[top].size();++i)
		{
			if (dis[x][E[top][i].num]>dis[x][top]+1) dis[x][E[top][i].num]=dis[x][top]+1,delta[x][E[top][i].num]=delta[x][top],pv[x][E[top][i].num]=(x==top)?E[top][i].num:pv[x][top],q.push(E[top][i].num);
			else if (dis[x][E[top][i].num]==dis[x][top]+1) Adder(delta[x][E[top][i].num],delta[x][top]);
		}
	}
	return;
}
int main()
{
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	int x,y,tres;
	dp[2][0]=dp[2][1]=1;
	for (int i=3;i<=N;++i)
	{
		Adder(dp[i][0],dp[i-1][1]);
		for (int j=2;j<=i-1;++j) Adder(dp[i][0],1ll*dp[j][0]*dp[i+1-j][0]%mod),Adder(dp[i][1],1ll*dp[j][0]*dp[i+1-j][1]%mod);
		Adder(dp[i][1],dp[i][0]);
	}
	for (int i=2;i<=N;++i)
	{
		F[i]=dp[i][0];
		for (int j=1;j<=i-1;++j) Adder2(F[i],-1ll*F[j]*(i-j+1)%mod);
	}
	c=read(),T=read();
	while (T--)
	{
		n=read(),m=read(),ans=inf,ans2=ans3=0;
		for (int i=1;i<=n;++i)
		{
			E[i].clear();
			for (int j=1;j<=n;++j) pv[i][j]=delta[i][j]=0;
		}
		for (int i=1;i<=m;++i) x=read(),y=read(),add(x,y,i);
		for (int i=1;i<=n;++i)
		{
			bfs(i);
			for (int j=1;j<=n;++j)
				if (j!=i)
					for (int k=0;k<E[j].size();++k)
						if (j<E[j][k].num&&E[j][k].num!=i&&pv[i][j]!=pv[i][E[j][k].num])
							ans=min(ans,dis[i][j]+dis[i][E[j][k].num]+1);
		}
		for (int i=1;i<=n;++i)
		{
			if (ans&1)
			{
				for (int j=1;j<=n;++j) DP[j]=0;
				for (int j=1;j<=n;++j)
					if (j!=i)
						for (int k=0;k<E[j].size();++k)
							if (j<E[j][k].num&&E[j][k].num!=i&&pv[i][j]!=pv[i][E[j][k].num]&&dis[i][j]==(ans>>1)&&dis[i][E[j][k].num]==(ans>>1))
								Adder(ans2,1ll*delta[i][j]*delta[i][E[j][k].num]%mod),Adder(DP[E[j][k].num],delta[i][E[j][k].num]),Adder(DP[j],delta[i][j]);
				for (int j=1;j<=n;++j) p[j]=j,ds[j]=dis[i][j];
				sort(p+1,p+n+1,cmp);
				for (int j=1;j<=n;++j)
					for (int k=0;k<E[p[j]].size();++k)
						if (dis[i][E[p[j]][k].num]+1==dis[i][p[j]])
							Adder(DP[E[p[j]][k].num],DP[p[j]]);
				for (int j=i+1;j<=n;++j)
					if (DP[j])
						Adder(ans3,1ll*delta[i][j]*MD2(DP[j]-1)%mod*F[dis[i][j]+1]%mod);
			}
			else
			{
				for (int j=1;j<=m;++j) DPS[j]=0;
				for (int j=1;j<=n;++j)
					if (j!=i)
					{
						tres=0;
						for (int k=0;k<E[j].size();++k)
							if (dis[i][E[j][k].num]==(ans>>1)-1)
								Adder(res[pv[i][E[j][k].num]],delta[i][E[j][k].num]),Adder(tres,delta[i][E[j][k].num]);
						for (int k=0;k<E[j].size();++k)
							if (dis[i][E[j][k].num]==(ans>>1)-1)
								Adder(ans2,1ll*MD2(tres-res[pv[i][E[j][k].num]])*delta[i][E[j][k].num]%mod*inv2%mod),Adder(DPS[E[j][k].data],MD2(tres-res[pv[i][E[j][k].num]]));
						for (int k=0;k<E[j].size();++k)
							if (dis[i][E[j][k].num]==(ans>>1)-1)
								Adder2(res[pv[i][E[j][k].num]],-delta[i][E[j][k].num]);
					}
				for (int j=1;j<=n;++j) p[j]=j,ds[j]=dis[i][j];
				sort(p+1,p+n+1,cmp);
				for (int j=1;j<=n;++j)
				{
					tres=0;
					for (int k=0;k<E[p[j]].size();++k)
						if (dis[i][E[p[j]][k].num]-1==dis[i][p[j]])
							Adder(tres,DPS[E[p[j]][k].data]);
					for (int k=0;k<E[p[j]].size();++k)
						if (dis[i][E[p[j]][k].num]+1==dis[i][p[j]])
							Adder(DPS[E[p[j]][k].data],tres);
				}
				for (int j=1;j<=n;++j)
					for (int k=0;k<E[j].size();++k)
						if (E[j][k].num>i&&dis[i][E[j][k].num]-1==dis[i][j]&&DPS[E[j][k].data])
							Adder(ans3,1ll*delta[i][j]*MD2(DPS[E[j][k].data]-1)%mod*F[dis[i][j]+2]%mod);
			}
		}
		ans2=1ll*ans2*fast_pow(ans,mod-2)%mod*dp[ans][1]%mod,Adder2(ans2,-ans3),printf("%d %d\n",-(ans+m-2),ans2);
	}
	return 0;
}
